#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack
{
    STDataType* data;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* ps);
void StackDestroy(Stack* ps);

void StackPush(Stack* ps, STDataType val);
void StackPop(Stack* ps);

STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);

bool isStackEmpty(Stack* ps);

void StackInit(Stack* ps)
{
    assert(ps);

    ps->data = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->data == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }

    ps->capacity = 4;
    ps->top = 0;
}

void StackDestroy(Stack* ps)
{
    assert(ps);

    free(ps->data);
    ps->data = NULL;
    ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType val)
{
    assert(ps);

    if (ps->top == ps->capacity) {
        STDataType* tmp = (STDataType*)realloc(ps->data, ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL) {
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            ps->data = tmp;
            ps->capacity *= 2;
        }
    }

    ps->data[ps->top] = val;
    ps->top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0); // 栈空时报错

    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0); // 栈空时报错

    return ps->data[ps->top - 1];
}

int StackSize(Stack* ps)
{
    assert(ps);

    return ps->top;
}

bool isStackEmpty(Stack* ps)
{
    assert(ps);

    return ps->top == 0;
}

typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));

    StackInit(&pq->s1);
    StackInit(&pq->s2);

    return pq;
}

void myQueuePush(MyQueue* obj, int x) 
{
    Stack* emptyS = &obj->s1;
    Stack* nonemptyS = &obj->s2;

    if (isStackEmpty(nonemptyS)) {
        emptyS = &obj->s2;
        nonemptyS = &obj->s1;
    }

    StackPush(nonemptyS, x);

}

int myQueuePop(MyQueue* obj) 
{
    Stack* emptyS = &obj->s1;
    Stack* nonemptyS = &obj->s2;

    if (isStackEmpty(nonemptyS)) {
        emptyS = &obj->s2;
        nonemptyS = &obj->s1;
    }

    while (StackSize(nonemptyS) > 1) {
        int top = StackTop(nonemptyS);
        StackPop(nonemptyS);
        StackPush(emptyS, top);
    }

    int ret = StackTop(nonemptyS);
    StackPop(nonemptyS);

    while (StackSize(emptyS) > 1) {
        int top = StackTop(emptyS);
        StackPop(emptyS);
        StackPush(nonemptyS, top);
    }

    return ret;
    
}

int myQueuePeek(MyQueue* obj) 
{
    Stack* emptyS = &obj->s1;
    Stack* nonemptyS = &obj->s2;

    if (isStackEmpty(nonemptyS)) {
        emptyS = &obj->s2;
        nonemptyS = &obj->s1;
    }

    while (StackSize(nonemptyS) > 1) {
        int top = StackTop(nonemptyS);
        StackPop(nonemptyS);
        StackPush(emptyS, top);
    }

    int ret = StackTop(nonemptyS);

    while (StackSize(emptyS) > 1) {
        int top = StackTop(emptyS);
        StackPop(emptyS);
        StackPush(nonemptyS, top);
    }

    return ret;
}

bool myQueueEmpty(MyQueue* obj) 
{
    return isStackEmpty(&obj->s1) && isStackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);

    free(obj);
    obj = NULL;
}

int main()
{
    MyQueue* pq = myQueueCreate();

    myQueuePush(pq, 1);
    myQueuePush(pq, 2);

    myQueuePeek(pq);

    myQueuePop(pq);

    printf("%d\n", myQueueEmpty(pq));


    return 0;
}
